\section{Overview of the Approach}  
\label{chapter:serimi1}
In this section, we present an overview of SERIMI, our solution for instance matching. 

\textbf{Data.} We use an RDF-based graph-structured model to accommodate different kinds of structured data. 
\begin{definition}[Data Graph] The data is conceived as a set of graphs $\mathbf{G}$. Let $U$ denote the set of Uniform Resource Identifiers (URIs) and $L$ the set of literals, every $G \in\mathbf{G}$ is a set of triples of the form $\langle s, p, o \rangle$, where  $s \in U$ (called subject), $p \in U$ (predicate) and  $o \in U \cup L$ (object). 
%form the vocabulary $V = U \cup L$. 
%
%\[
%Pred(s, G)=\{p | \langle s,p,o \rangle \in G\}
%\]
\end{definition}

Every instance (set of instances) is represented as a set of triples.  

\begin{definition}[Instance Representation] It is  defined as:  $IR(G, S) = \{\langle s, p, o \rangle$ $| \langle s, p, o \rangle \in G, s \in S \}$, where  $G$ is a graph and $S$ a set of instances in $G$. It yields a set of triples in which $s \in S$ appears as the subject. We denote the set of objects associated with an instance $s$ over the predicate $p$ in $G$ as $O(s,p,G)$, with $O(s,p, G)=\{o | \langle s,p,o \rangle \in G\}$.
\end{definition} 
 

The representation of a single instance $s$ is $IR(G,$ $\{s\})$. 
%We will use the terms instance and instance representation interchangeably from now on. 
%For simplicity, we use in this work the outgoing edges $(s, p, o)$ of a resource $s$ to form its representation $IR(G, \{s\})$.
% However, other types of representations that may include incoming edges, as well as more complex structures in the data (e.g. paths instead of edges), are applicable. 


\begin{figure}[h]
\centering
\includegraphics[width=1\textwidth]{./Chapters/Chapter3/overview.pdf}
\caption{The instance matching in SERIMI.} 
\label{fig:overview}
\end{figure} 

The process of instance matching performed by SERIMI is illustrated in Fig.\ \ref{fig:overview}. SERIMI focuses on the problem of \emph{instance matching across heterogeneous datasets}. 
%The inputs thus represent different datasets and the goal is to find matches between datasets. 
In particular, the inputs are conceived to be partitioned into two datasets, the source $S$ and target $T$. For every instance in $s \in S$, the goal is to find matching instances $t \in T$, i.e. $s$ and $t$ refer to the same real-world object. This matching is performed in two main steps, candidate selection and match refinement. 

\textbf{Candidate Selection.}  For each $s \in S$,  we firstly perform a low cost candidate selection step to obtain a candidate set $C(s) \subset T$. The union of all candidate sets is denoted as $C(S)=\{C(s) | s \in S \}$. This step reduces the number of comparisons needed to find matches between the source and target, i.e., from a maximum of $|S| \times |T|$ comparisons to $|S| \times |C(s)^{max}|$, where $C(s)^{max}$ is the set with the largest number of candidates among all candidate sets in $C(S)$. 
Existing blocking techniques~\citep{hernandez_merge/purge_1995,mccallum_efficient_2000,papadakis_efficient_2011} can be used to quickly select candidates. Typically, a predicate (a combination of predicates) that is useful in distinguishing instances is chosen, and its values are used as blocking keys. In this setting of cross-dataset matching, a predicate in the source is chosen (e.g. \verb+rdfs:label+) and its values (e.g. 'San Francisco'.) are used to find target candidate instances that have the same values in their predicates.
%In particular, we select attributes with entropy higher than a threshold. Given the attribute $a$ and its literal values $O(a) = \{o | (s,a,o) \in G\}$, let $p$ be the probability mass function of $a$, then the entropy of $a$ is $H(a)=-\sum_{o \in O(a)} p(o)log_2p(o)$.
Using the current example, the candidates matches for $S$ =\{\verb+nyt:2223+, \verb+nyt:5962+, \verb+nyt:5555+\} would be $C(\verb+nyt:2223+) =$ \{\verb+db:San_Francisco+\} , $C(\verb+nyt:5962+) =$ \{\verb+db:Belmont_+\verb+California+, \verb+db:Belmont_+ \verb+France+\} and $C(\verb+nyt:5555+) =$ \{\verb+db:San_Jose_+ \verb+California+,  \verb+db:San_Jose_+\verb+Costa_Rica+\}, in all sets the candidates share the same value of the predicate  \verb+rdfs:label+  with the source instance.
 
After the candidates are determined, a more refined matching step is performed to find correct matches, $M(s) \subseteq C(s)$. For this, state-of-the-art approaches perform more complex \textit{direct matching}, which instead of a simple blocking key, involves a combination of weighted similarity functions defined over several predicate values \citep{DBLP:journals/pvldb/WangLYF11,DBLP:journals/pvldb/SuchanekAS11}. 
%In this work, we introduce a complementary matching paradigm called \textit{class-based matching} that is used in combination with direct matching. 


\textbf{Direct Matching.} In direct matching, two given instances $s$ and $t$ are directly compared. They are considered as a match when their similarity, $sim(s,t)$, exceeds a threshold $\delta$. Typically, $sim(s,t)$ is captured by an \emph{instance matching scheme}, which is a weighted combination of similarity functions (Edit Distance, Jaccard, ect.) defined over the predicate values of $s$ and $t$ \citep{DBLP:journals/pvldb/WangLYF11,DBLP:journals/pvldb/SuchanekAS11}:  

\begin{equation}
sim(s,t) = \sum_{p \in P} {w_p\cdot sim(O(s,p,S), O(t,p,T))}  > \delta
\end{equation}


%Then, whether this match computed by the algorithm is indeed correct or not, i.e.\ refer to the same real-world entity or not, is verified by the ground truth.

The above scheme assumes that $s$ and $t$ have some common predicates $p$ based on which they can  be directly compared (e.g. \verb+rdfs:label+, \verb+db:incountry+). In the heterogeneous setting, $S$ and $T$ may exhibit differences in their schemas. Instead of assuming $p$, more generally, we can  define the instance matching problem in this setting based on the notion of comparable predicates $\langle p_s,p_t\rangle$. The predicate $p_s$ is a predicate in $S$, whose values can be compared with those of $p_t$, a predicate in $T$. 

For example, the instance \verb+nyt:4232+ does not share any predicate with the DBPedia instances but we can assume that  the predicate \verb+nyt:prefLabel+ ($p_s$) is comparable to the predicate \verb+rdfs:label+ ($p_t$) because they have a similar range of values. Solutions, which specifically target this setting of cross-datasets matching, employ automatic schema matching or manually find the pairs of comparable predicates \citep{DBLP:journals/pvldb/SuchanekAS11,hu_bootstrapping_2011,Song:2011:AGD:2063016.2063058}.  
%Predicates are comparable when they represent the same concept. More generally, they are comparable when matches in their values represent useful evidences for instance matching (thus, finding comparable predicates is a more general problem than schema matching, where the goal is to find predicates representing the same concept). \todo{maybe use this as motivation for our solution to the mapping problem. I DID NOT UNDERSTAND THIS COMMENT} 
Let $P_{st}$ be the set of all comparable predicates, we can define the instance matching scheme for this setting as follows: 

\begin{equation}
%\footnotesize
sim(s,t) = \sum_{\langle p_s,p_t \rangle \in P_{st}} {w_{\langle p_s,p_t \rangle} sim(O(s,p_s,S), O(t,p_t,T))} > \delta
\label{eq:sim}
\end{equation} 

\textbf{Class-Based Matching.} The direct matching paradigm has proven to be useful in the homogeneous setting where instances share some common predicates $p$. In the heterogeneous setting, we showed above that this paradigm would require some pairs of comparable predicates. Since these direct overlaps at the level of predicates (or values) between instances may be
%do not exist, or are 
%too few 
too small to perform matching in the heterogeneous setting, we propose class-based matching. 

In combination with direct-matching, class-based matching can be applied on top of the candidate selection step. As illustrated in Fig.\ \ref{fig:overview}, candidate selection yields a set of candidates $C(S)$, which is then further refined by a module that combines class-based and direct matching to obtain $M(S)= \{M(s_i), ..., M(s_n)\}$, where $\forall i. M(s_i) \subseteq C(s_i) \in C(S)$.  

Considering our example, the solution set $M(S)$ for those candidate sets would be: $M(S)=$\{$M$ (\verb+nyt:2223+), $M$(\verb+nyt:5962+), $M$(\verb+nyt:5555+)\}, where $M$(\verb+nyt:2223+)=\{\texttt{db:San\_} \texttt{Francisco}\}, $M$(\verb+nyt:5962+)=\{\verb+db:Belmont_+\verb+California+\}  and $M$(\verb+nyt:555+\verb+5+)=\{\texttt{db:San\_} \texttt{Jose\_California}\}.


Let $M^*(S)$ be the optimal result that contains only correct matches for every $s \in S$. Class-based matching does not directly compare $s$ with a candidate $t \in C(s)$. Rather, it determines whether $t$ is a match or not based on its class membership, i.e. whether it ``belongs to'' $M^*(S)$, which acts as an instance-based representation of the class of interest (CoI). More precisely, it uses an approximation of this class because $M^*(S)$ is not given but stands for the actual result to be determined by instance matching. In this way, only information from the target is used for matching, namely the candidates $t \in C(s) \in C(S)$ and the CoI $M^*(S)$ captured as subsets of these candidates. 

For example, \verb+db:Belmont_France+ is not considered part of the solution because it is less similar than the instance \verb+db:Belmont+ to the elements in the sets in $M(S)$ (i.e., \verb+db:San_+\verb+Francisco+ and  \verb+db:San_Jose_+ \verb+California+). Precisely,  the candidate instance \verb+db:Belmont+ shares the predicate \verb+db:country+ and value \verb+db:Usa+ with the instance \verb+db:San_+\verb+Francisco+, therefore, it is more likely to be a correct match than the candidate \verb+db:Belmont_France+.

This matching builds upon the observation that matching is performed for a class of source instances. That is, all $s \in S$ belongs to a specific class, the CoI (even when the input $S$ captures different classes, it can be partitioned into sets of instances representing specific classes \citep{typifier}). Consequently, the candidate instances $t \in C(s) \in C(S)$ that are correct matches for $s \in S$ should also belong to a class that corresponds to this CoI. 

For example, consider a set of source instances $S$  of the type \verb+Drug+. Class-based matching exploits the intuition that correct matches in the target must belong to a class that corresponds to \verb+Drug+, e.g. \verb+Medication+. However, our previous study of heterogeneous data shows that class information is often missing or might be too general to be useful \citep{typifier}. That is, the class to which $t$ (or $s$) belongs to might not be explicitly given in the target (source); or the class to which $t$ belongs is specific (e.g. \verb+Medication+) while the one $s$ belong to is much more general (e.g \verb+Product+). Hence, classes might be missing or too different in granularity such that a direct matching at the class-level is not always possible.

Addressing this, class-based matching employs a latent, \emph{instance-based representation} of the class that is determined during the instance matching process. In this example, we would need a representation for the class \verb+Medication+, for which we employ an approximation of $M^*(S)$ that shall capture all instances of the type \verb+Medication+. Because the matching is non-direct, the class to which $s$ belongs to is not needed but the candidates $t \in C(s) \in C(S)$ and $M^*(S)$. The problem is how to obtain a good approximation that captures all instances of the CoI, which coincides with the actual problem of instance matching, i.e. finding the optimal results $M^*(S)$. The main idea behind class-based matching can be formalized as follows:

\begin{definition}[CoI, Class-based Matching]  To find the best representation for the CoI and solution for the class-based matching problem, respectively, amounts to computing
\begin{equation}
%\footnotesize
\begin{aligned}
&  M^*(S) \approx \argmax_{M(S) \in \mathbf{M}} \frac{\sum_{M(s) \in M(S)}\sum_{t \in M(s)} Sim(t, M(S))}{\sum_{M(s) \in M(S)} |M(s)|} + Z(S) \\
& \text{Subject to:} \\
&   Sim(t, M(S))  > \delta \text{ and } \\
& M(S)=\{M(s) |  s \in S : M(s) \subseteq C(s) \in C(S)\}
\end{aligned}
\label{eq:opt}
\end{equation}

where $\mathbf{M}$ is the set containing all possible $M(S)$ as elements, $Sim(t, M(S))$ is an arbitrary function (e.g., Jaccard) that returns the similarity between an instance $t$ and an instance-based class representation $M(S)$, $\delta$ is a similarity threshold and 

\begin{equation}
%\footnotesize
Z(S)= \frac{\sum_{s \in S}H(s)}{|S|} 
\text{, with } H(s)= \left\{ 
  \begin{array}{ll}
     0 &   \text{if } |M(s)|=0 \\
     1 &  \text{otherwise}
  \end{array} \right. 
\end{equation} 
 
\end{definition}
Note that $Sim(t, M(S))$ operates over \textit{features} extracted from the instance t and instances in the sets in $M(S)$. This will be detail further, in our proposed solution to this problem.

Also note $Z(S)$ is simply an auxiliary term introduced to deal with the general case where $M(s)$ might be empty. It helps to score higher a solution set  $M(S) \in \mathbf{M}$ where the majority of $M(s) \in M(S)$ has cardinality higher than zero; therefore, avoiding solution sets with many empty matches. This term is not needed in the setting where there always exists at least one candidate for a given source instance $s$. In this case, we can simplify Eq.\ \ref{eq:opt} to:
%instance assume that the matches are one-to-one match or one-to-many, we can constrain $|M(s)|=1$, or $|M(s)|>0$, respectively. In those cases, 
\begin{equation}
\begin{aligned}
& M^*(S) \approx \argmax_{M(S) \in \mathbf{M}} \frac{\sum_{M(s) \in M(S)} \sum_{t \in M(s)} Sim(t, M(S))}{\sum_{M(s) \in M(S)} |M(s)|}   \\
& \text{Subject to:} \\
&Sim(t, M(S))  > \delta, \\
& |M(s)|>0  \text{ and } \\
& M(S)=\{M(s) |  s \in S : M(s) \subseteq C(s) \in C(S)\}
\end{aligned}
\label{eq:opt2}
\end{equation}
  

Intuitively, the idea is to find an approximate solution $M^*(S) \in \mathbf{M}$, which contains at least one candidate for every source instance $s$ (c.f. $|M(s)|>0$ in Eq. 5). Comparing to all the other candidate solutions in $\mathbf{M}$, $M^*(S)$ is the most similar to the instances it consists of (c.f. $Sim(t, M(S))$ in Eq. 5). That is, $M^*(S)$ is not only the result but at the same time, acts as the CoI that is compared with the candidates instances $t \in C(s) \in C(S)$. 

Solving this problem requires finding the threshold $\delta$, enumerating of all possible sets $\mathbf{M}$, and determining the optimal $M^*(S)$. Since this enumeration could be very large, i.e., $|\mathbf{M}|=2^{\sum_{s \in S}|C(s)|}$ (because $|M(S)|=|S|$), we propose an approximate solution to this that does not require a full enumeration. Also, we show how to obtain a more compact representation of $M^*(S)$ and to automatically choose $\delta$. 

%\textbf{Class-Based Matching.} The direct matching paradigm has proven to be useful in the homogeneous setting where instances share some common predicates $p$. In the heterogeneous setting, we showed above that this paradigm would require some pairs of comparable predicates. Since these direct overlaps at the level of predicates (or values) between instances may do not exist, or are too few to perform matching in the heterogeneous setting, we propose class-based matching. This matching can be applied on top of candidate selection, or after a refined matching step based on direct matching as discussed.  The result of either of these two steps can be conceived as a set of candidates, $C(s)$, which is further refined by class-based matching to obtain $M(s)$.  
%
%\begin{definition} Candidate Set - Let S and T be the set of source and target data. A candidate set $C(s)$ for $s \in S$, is defined  as: $C(s) = \{t | \alpha >  Sim(s,t) < \delta \}$.
%\end{definition}
%

%Class-based matching does not directly compare $s$ with a candidate $t \in C(s)$. It determines whether $t$ is a match or not based on its class membership, which is derived using information in the target, namely the candidate sets $C(S) = \{C(s) | s \in S \}$. This matching builds upon the observation that matching is performed for a class of instances. That is, all $s \in S$ belongs to a specific class, called the class of interest (even when the input $S$ captures different classes, it can be partitioned into sets of instances belonging to specific classes \todo{cite our paper}). The idea here is to conceive $C(S)$ as a class (or more precisely, to employ $C(S)$ as an instance-based representation of a class). Due to the correspondence between elements $s \in S$ and $t \in C(S)$, the class of $t$ must correspond to the class of $s \in S$. A candidate $t \in C(S)$ is considered as a match only when it belongs to this class of interest. This is the case when $t$ shares the characteristics captured by $C(S)$, i.e. $t$ exhibits characteristics that are common to instances in $C(S)$. 

%For instance, sources instances $S$ are of the type Drug. Class-based matching exploits the intuition that correct matches in the target must belong to a class that corresponds to Drug, e.g. Medication. As a representation for the class of Medication, we use $C(S)$. Candidates that match $C(S)$ are inferred to be of the type Medication and thus, considered as matches. 

%During this process, $t$ is not compared with one single candidate but all candidates in $C(S)$. In fact, no information from the source is directly used, as for refinement, we actually compare every candidate in $C(S)$ with $C(S)$. That is, we do not perform direct matching between source and target but only use information in the target for further refinement. The scheme for this matching paradigm can be simply stated as $$sim(t, Class(s)) > \delta.$$  The main problems are how to obtain a representation of the class of interest, $Class(s)$, and what threshold to be used. 

%
%\begin{definition} Class-Based Matching - If set of source instances $S' \subset S$ has a $CTP$, and the target set $M$ has a $CTP$  where  $\forall s \in S'$, $\exists t \in M \land t \in C(s)$ then $t \in M$ forms a Same-as relation to $s \in S$
%\end{definition}
%
% In the next sections, we describe our solution for the direct matching and class-based matching 
%over heterogeneous data.

\textbf{SERIMI.} This chapter focuses on class-based matching. Existing works are adopted for the candidate selection and direct matching components of SERIMI. As discussed before,  the candidate sets $C(s) \in C(S)$ are determined for each instance $s \in S$ using a predicate value of $s$ as key. The predicate is selected automatically based on the notion of coverage and discriminative power of predicates, also employed by \citep{Song:2011:AGD:2063016.2063058}. Then, for direct matching, we use simple schema matching to compute comparable predicates $P_{st}$. The matching between a source instance $s$ and a target instance $t$ is then performed using values of predicates in $P_{st}$. As $sim(s,t)$, we use Jaccard similarity. 
%These predicates We use Jaccard as similarity function where we compared the set of bigrams $W_s$ and $W_t$ of the values of the predicate pair $\langle p_s, p_t \rangle\in P_{st}$. 
The main difference to existing works lies in the selection of the threshold: 
%Then, an instance $t$ is considered as a correct match for $s$ if $sim(s,t) \geq \delta$ 
for this, we use the same method that we propose for class-based matching. 
%This statistics-based method be discussed in detail. 

%or its score $sim(s,t)$ is the top-1 among all instances $ t \in C(s)$ (called \textit{TOP-1 approach}). The Top-1 approach makes sense for those cases in the heterogeneous scenario where datasets are duplicate-free, i.e., when the one-to-one mapping between source and target exists. 

We observe in the experiments that a simple combination of direct- and class-based matching was sufficient to produce good results. In SERIMI, they are treated as black boxes that yield two scores. SERIMI multiplies and normalizes these scores to obtain a value in [0,1]. 
%, and selected the correct matches $M$ using the Threshold or TOP-1 approach. In the next section, we describe how we compute the class-based matching score.
